public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {100,4,3,5,1,8,2,7,6,9,10};
        quickSort(arr);
        for(int i : arr) {
            System.out.print(i + " ");
        }
    }

    private static void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private static void quick(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int ret = partitions(arr, start, end);

        quick(arr, ret + 1, end);
        quick(arr, start, ret - 1);
    }

    private static int partitions(int[] arr, int left, int right) {
        int i = left;
        int temp = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= temp) {
                right --;
            }
            while (left < right && arr[left] <= temp) {
                left ++;
            }
            Swap(arr, left, right);
        }
        Swap(arr, i, left);
        return left;
    }

    private static void Swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}
